1. Field
The following relates to rendering, using ray tracing, two-dimensional representations of three-dimensional scenes, and more particularly to accelerating intersection testing of rays with acceleration structures.
2. Related Art
Rendering photo-realistic 2-D images from 3-D scene descriptions with ray tracing is well-known in the computer graphics arts. Ray tracing usually involves obtaining a scene description composed of geometric shapes, which describe surfaces of structures in the scene, and can be called primitives. A common primitive shape is a triangle. Objects can be composed of one or more such primitives.
The primitives can be associated with textures and other information that instructs a computer how light hitting that primitive should be affected by qualities of the primitive. In other words, a model of a physical environment is produced; the model may be designed to produce realistic results for conditions familiar to humans, or the model may be designed to achieve other results as desired. Ray tracing can produce such photo-realistic images, including realistic shadow and lighting effects, because ray tracing can model the physical behavior of light interacting with elements of a scene. However, ray tracing is also known to be computationally intensive, and at present, even a state of the art graphics workstation requires a substantial amount of time to render a complicated scene using ray tracing, and real-time high quality and resolution rendering with ray tracing is still difficult to achieve.
A computationally intensive part of completing a rendered 2-D representation of a 3-D scene is determining which rays intersect which primitives (can be called intersection testing). This is because a complex scene can have hundreds of thousands, or even millions of primitives, and many thousands (or more) of rays need to be intersection tested in the scene. Directly testing each ray against each primitive has been found to be computationally more expensive than strategies that introduce an acceleration structure into the 3-D scene, such that the scene is subdivided for intersection testing. Such subdivision provides the effect that a ray can be tested first against the acceleration structure to determine whether the ray possibly can intersect a given primitive or set of primitives because it intersects an element of the acceleration structure bounding the primitive(s). Then, if that ray intersects a bounding acceleration structure, there is a possibility that ray also intersects primitives bounded by it. Intersection testing can then be done to determine whether the ray intersects any of those primitives. An acceleration structure can include several layers of increasingly smaller spatial subdivisions; acceleration structures can be hierarchical.
A wide variety of strategies exist for subdividing a scene with an acceleration structure to aid in intersection testing. A currently popular strategy is called a k-d tree, where k can be an integer number, usually 3 for a 3-D scene. A k-d tree can be formed by repetitively cutting a 3-D scene using a cutting plane for each of the k dimensions. For the common 3-D tree, eight smaller boxes (can be cubes) result from each cutting step. Often, the scene is cut for each ray to an acceptably small volume so that a number of primitives in the volume is small enough to test them for intersection with the ray. Then, the ray can be tested for intersection with any primitives in that volume, and if not, it can be passed to a next volume that the ray would enter. The next volume also can be identified by a series of cutting planes to again identify a small volume in which to test primitives. Then, intersection testing can again be performed.
A k-d tree is an attractive acceleration structure, because the acceleration structure itself is easy to construct and use, and the tree can be represented efficiently in memory. In other words, the cutting plane tests used in the k-d d tree are, relative to other strategies, computationally inexpensive to determine and use in rendering. Also, relatively small amounts of data are required to represent a k-d tree, so that memory requirements to store the data and bandwidth requirements to access the data can compare favorably to other acceleration structures.
A variety of other approaches to using acceleration structures are known in the literature. For example, it has been known to use spheres as shapes to bound primitives. However, further innovation in the area of such acceleration structures remains desirable because such accelerating intersection testing is an aspect than can help achieve increased resolution and frame rates for ray tracing rendering. Also, other qualities can be desirable in acceleration structures, for example, an acceleration structure that may perform well in a static scene may not perform well for accelerating a sequence of images having the same or similar scene objects under dynamic conditions. Therefore, further advancements in acceleration structures are desired.